#encoding=utf-8
'''
   [54,226,93,17,77,31,44,55,20] 升序

   [54,     226,93,17,77,31,44,55,20]
   [54,226,     93,17,77,31,44,55,20]
   [54,93,226,     17,77,31,44,55,20]
   [17,54,93,226,     77,31,44,55,20]
   [17,54,77,93,226,     31,44,55,20]

   发现和前面一个元素比较 后大 交换
'''

def insert_sort(alist):
    n = len(alist)
    for j in range(1,n): #n-1 n
        i=j
        while i>0:  #和有序列表中每个元素进行比较（从最后一个开始）
            if alist[i]<alist[i-1]: #如果当前元素比前一个元素小，则进行交换
                alist[i],alist[i-1]=alist[i-1],alist[i]
            else: #否则已经是有序列表，不需要交换了，则退出循环
                break
            i-=1

if __name__ == "__main__":
    alist=[54,226,93,17,77,31,44,55,20]
    print("原列表:",alist)
    insert_sort(alist)
    print("插入排序后的列表:",alist)

'''
时间复杂度：最坏：n*n=O(n^2);最优：n*1=O(n)
稳定性：稳定
'''